package backtrack;

import java.util.ArrayList;
import java.util.List;

public class Solution46 {
    public List<List<Integer>> result=new ArrayList<>();
    public List<Integer> track = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        backTrack(nums,visited);
        return result;
    }

    public void backTrack(int[] nums,boolean[] visited){

        if (track.size()== nums.length){
            result.add(new ArrayList<>(track));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            //做出选择
            if (!visited[i]){
                track.add(nums[i]);
                visited[i] = true;
            }else {
                continue;
            }
            backTrack(nums, visited);

            //撤销选择
            track.remove(Integer.valueOf(nums[i]));
            visited[i] = false;
        }
    }



    public static void main(String[] args) {
        Solution46 solution46 = new Solution46();

        int[] nums = new int[3];
        for (int i = 0; i < nums.length; i++) {
            nums[i]=i+1;
        }

        List<List<Integer>> lists = solution46.permute(nums);

        for (List<Integer> list : lists) {
            System.out.println("list.toString() = " + list.toString());
        }
    }
}
